It is generally acknowledged that complex integrated circuits cannot be manufactured with an absolute assurance that they will work perfectly. Even if design failures are ignored, minor processing variations may cause small portions of the integrated circuit to malfunction and to produce incorrect output for a given set of inputs. Often, the failures are subtle and will produce erroneous outputs only for a small fraction of possible input values. As a result, the practice has developed of electronically testing each integrated circuit that is fabricated. Unfortunately, complex integrated circuits have a large number of input pins, so large that it becomes economically unfeasible to test all possible input patterns. Instead, the practice has developed of subjecting the integrated circuits to a large number, sometimes more than one million, of input test vectors and monitoring the resultant outputs. Any incorrect outputs indicates a faulty chip. Usually, the sequence of test vectors is considered to be random although in fact the sequence is only psuedo-random because the sequence is determined and is the same for testing all chips within a product line. Random pattern testing has numerous potential advantages, including cheaper testing, better testing and the possibility of a self test. However, the sequence of test vectors is not exhaustive and a determination should be made of the probability that a given number of random test vectors will uncover a particular fault. The average value of this probability over all faults is called the fault coverage for such a test and the actual fault coverage needs to be determined separately for every new design.
Testability is a more generic term for fault coverage. A very high numerical value for fault coverage indicates a good testability of a design. There exist several techniques for determining the random pattern testability of given faults, such as a single stuck-at fault, in combinational logic. One possible technique is simulation, that is, a computer simulation of the complete design with a fault selectively inserted at one point. Then, test sequences are generated and based upon extensive runs the fault coverage is determined. Any design, even a design incorporating a memory, can be simulated on a sufficiently powerful simulator. The cost of such a simulator depends on factors such as the power of the simulator and the length of the test sequence necessary to reach an acceptable fault coverage. For many designs, simulation is a practical technique for determining random pattern testability.
For other designs, however, the cost of a complete fault simulation may become prohibitive. Such designs may require analytical techniques such as the input signal probability approach described by Parker et al. in a technical article entitled "Analysis of Logic Circuits with Faults Using Input Signal Probabilities", appearing in IEEE Transactions on Computers, May 1975, pp. 573-578 or the cutting algorithm described by Savir et al. in a technical article entitled "Random Pattern Testability", appearing in Digest, 13th Annual Fault-Tolerant Computing Symposium, June 1983, pp. 80-89. However, these analytic techniques rely on the validity of various Boolean equalities and are, thus, not automatically applicable to designs that contain memories, such as RAMs, embedded in surrounding logic. If the combined memory and logic design is sufficiently simple, for example, if there is not logic on the output side of the RAM, the problem can still be treated analytically, as has been described by McAnney et al. in a technical article "Random Pattern Testing for Data-Line Faults in an Embedded Multiport Memory", appearing in the Proceedings of the International Test Conference, 1985, pp. 100-105. Unfortunately, the simplicity required in the prior art to analytically treat embedded memory is too restrictive for realistic designs.